import {Compare, compareType, defaultCompare} from "../utils/Compare";
import {swap} from "../utils/utils";

interface HeapInterface<T> {
    compare: compareType<T>;
    heap: Array<T>;

    insert(value: T): boolean;

    extract(): T | undefined; // 移除最小值或者最大值
    find(): T | undefined;
}

abstract class Heap<T> implements HeapInterface<T> {
    compare: compareType<T>;
    heap: Array<T>;

    constructor(compareFn: compareType<T> = defaultCompare) {
        this.compare = compareFn;
        this.heap = new Array<T>();
    }

    static getLeftIndex(index: number): number {
        return 2 * index + 1;
    };

    static getParentIndex(index: number): number | undefined {
        if (index === 0) {
            return undefined;
        }
        return Math.floor((index - 1) / 2)
    };

    static getRightIndex(index: number): number {
        return 2 * index + 2;

    };

    abstract insert(value: T): boolean;

    abstract extract(): T | undefined;

    find(): T | undefined {
        return this.isEmpty() ? undefined : this.heap[0]
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.size() === 0;
    }

}


export class MinHeap<T> extends Heap<T> {
    insert(value: T): boolean {
        if (value != null) {
            this.heap.push(value)
            this.siftUp(this.heap.length - 1);
            return true;
        }
        return false;
    }

    extract(): T | undefined {
        if (this.isEmpty()) {
            return undefined
        }

        if (this.size() === 1) {
            return this.heap.shift();
        }

        const removeValue = this.heap[0];

        this.heap[0] = <T>this.heap.pop();

        this.siftDown(0);
        return removeValue;
    }

    siftDown(index: number) {
        let el = index;
        let left = Heap.getLeftIndex(el);
        let right = Heap.getRightIndex(el);
        let size = this.size();
        if (left < size && this.compare(this.heap[el], this.heap[left]) === Compare.BIGGER_THAN) {
            el = left;
        }
        if (right < size && this.compare(this.heap[el], this.heap[right]) === Compare.BIGGER_THAN) {
            el = right
        }
        if (index !== el) {
            swap(this.heap, index, el)
            this.siftDown(el);
        }

    }

    siftUp(index: number) {
        let parentIndex = Heap.getParentIndex(index);
        // 如果插入的值 比 父元素小
        // 也就是 父元素 > 子元素
        // 说明不符合 最小堆(最小堆中父元素是小于子元素的), 则需要进行交换
        while (index > 0 && parentIndex && this.compare(this.heap[parentIndex], this.heap[index]) === Compare.BIGGER_THAN) {
            swap(this.heap, index, parentIndex);
            index = parentIndex;
            parentIndex = Heap.getParentIndex(index);
        }
    }

}

export class MaxHeap<T> extends MinHeap<T> {
    constructor(compare: compareType<T> = (a: T, b: T) => defaultCompare(b, a)) {
        super(compare);
    }
}


function buildMaxHeap<T>(arr: Array<T>, compare: compareType<T>) {
    for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
        heapify(arr, i, arr.length, compare);
    }
    return arr;
}

function heapify<T>(arr: Array<T>, index: number, heapSize: number, compare: compareType<T>) {
    let el = index;
    let left = Heap.getLeftIndex(el);
    let right = Heap.getRightIndex(el);
    let size = heapSize;
    if (left < size && compare(arr[el], arr[left]) === Compare.LESS_THAN) {
        el = left;
    }
    if (right < size && compare(arr[el], arr[right]) === Compare.LESS_THAN) {
        el = right
    }
    if (index !== el) {
        swap(arr, index, el)
        heapify(arr,el,heapSize,compare);
    }
}

function heapSort<T>(arr: Array<T>, compare: compareType<T> = defaultCompare) {
    let heapSize = arr.length;
    buildMaxHeap(arr, compare);
    while (heapSize > 1) {
        swap(arr, 0, --heapSize);
        heapify(arr, 0, heapSize, compare);
    }
    return arr
}

const arr = [7,6,3,5,4,1,2]
heapSort(arr)
console.log(arr)
